This invention relates to the field of assembly of mechanical systems, specifically automated planning of a sequence of steps for assembly or disassembly of a mechanical system comprising a plurality of parts.
Product creation has traditionally been separated into at least two stages: first a designer specifies the geometry and physical qualities of the finished product to perform the function needed, then a manufacturing engineer takes over and tries to find a way to manufacture the product. If it is too difficult to manufacture, the product is sent back for redesign, and the cycle repeats. Because the design of the product and the design of the manufacturing process are only loosely coupled, many cycles may be required to find a satisfactory design, while the final artifact usually remains more expensive to build than necessary.
Concurrent design of a product and the process to make it is one way to address this problem. In concurrent design, the manufacturing process is created simultaneously with the product plans, so that constraints arising from manufacturing can be directly incorporated into the product design, thereby reducing global iteration. In addition, automated tools support this process at a high level. Human engineers use computer workstations to build a shared product model, which is continually updated and critiqued to give the designers manufacturing and servicing feedback about the design. Some of the tools affecting the developing product model are computer programs, which do process planning, check for consistency, and perform other tasks previously left to human engineers.
A proficient assembly planner is an integral part of a concurrent design system. A good assembly process can reduce assembly time, raise quality and reliability, allow greater flexibility in responding to equipment failures, and reduce capital costs for robots and fixtures. Furthermore, many of the manufacturing constraints that influence a product design come from the need to assemble constituent parts of the product. For example, the assembly scheme of a product influences the tolerances imposed on individual parts, the shape of mating surfaces, and the design of fasteners.
Assembly planning for production is typically performed by an industrial engineer. Service and repair technicians devise reasonably efficient and error-free disassembly and reassembly plans on the fly. However, assembly planning is complicated and time-consuming for a human. Besides avoiding the high cost of an engineer's time, an automated assembly planner can accelerate the generation of an assembly plan. With higher planning speed comes faster introduction of manufacturing constraints into the design process, as well as shorter time-to-market.
Intuition, rules of thumb, and approximate reasoning help human engineers to quickly find good assembly plans, but they also may lead them to overlook the best assembly plan. An automated assembly planner can evaluate many feasible assembly plans to ensure that no better procedure exists. Furthermore, by exploring the set of alternative plans generated by the planner, or "plan space," a designer can come to a better understanding of the manufacturing aspects of the design.
Current automated assembly planners rely on a broad array of techniques, each addressing certain aspects of the problem. These techniques can be roughly divided into Artificial Intelligence approaches to planning, planners specifically designed for assembly sequencing, physical reasoning to validate single assembly operations, and computational geometry approaches.
ARTIFICIAL INTELLIGENCE PLANNING
STRIPS, NOAH, and SIPE are examples of traditional Al (artificial intelligence) planning systems. See, e.g., Fikes et al., "Strips: A new approach to the application of theorem proving to problem solving," Artificial Intelligence, 2:189-208, 1971; Wilkins, "Domain-independent planning: Representation and plan generation," Artificial Intelligence, 22(3):269-301, 1984. The blocks world was an early Artificial Intelligence ("Al") planning system consisting of blocks that could be stacked and unstacked. NOAH was originally aimed at supplying instructions to a human to repair an air compressor, including disassembly and assembly plans. In typical domains for these planners, actions are quite varied (for instance moving between rooms, grasping objects, recharging batteries), while geometric constraints are expressed in a few simple logical predicates, such as ON(A, B) or IN(pen, Rooml). In contrast, an automated assembly planner need only consider a few types of operations joining two subassemblies, certain fixturing operations), while the constraints arising from geometric models are so complicated that expressing them in a logical notation would be exhausting and inefficient. Hence Al planning techniques can be ill-suited to the geometric reasoning required for automated assembly planning.
ASSEMBLY SEQUENCING
A number of planning systems have been targeted specifically at assembly sequencing. An early planning system started with a liaison graph of the assembly, which is a graph of connections between the parts. Liaisons usually, but not always, involve contact between the two parts. An assembly sequence corresponds to a particular order in which the liaisons can be established. Geometric reasoning was supplied by a human, who answered carefully constructed, yes-no questions about whether certain liaisons can be established before or after others. From the answers to these questions, the assembly sequences for the product were inferred.
A later planning system reduced the number of questions and answers required to represent the physical knowledge. DeFazio et al., "Simplified generation of all mechanical assembly sequences," IEEE Journal of Robotics and Automation, RA-3(6):640-658, 1987. The user answered each question with a logical formula characterizing the situations in which a liaison can be established. Unfortunately, these formulas became complicated and difficult to create accurately for realistically large assemblies.
A planning system at Carnegie-Mellon University used disassembly planning to automatically generate assembly sequences. Disassembly planning computes a way to disassemble the product, then reverses the sequence to produce an assembly sequence. To identify a single feasible operation, the method generates all possible subassemblies and tests the operation removing each subassembly from the rest of the assembly. An operation is tested by a predicate that includes geometric, mechanical, and stability checks. Local freedom was the main geometric test computed in the Carnegie-Mellon system; a subassembly is locally free when it can move a small distance relative to the rest of the assembly considered as a solid. In this generate-and-test approach, a number of candidate operations exponential in the number of parts can be generated before a feasible operation is found, rendering the approach impractical for large assemblies.
Wolter computed linear assembly sequences for a product, in which each operation joins a single part to a subassembly. Wolter, "On the automatic generation of assembly plans," in Computer-Aided Mechanical Assembly Planning, de Mello and Lee, editors, pages 263-288, Kluwer, 1991. The sequences were optimized according to certain criteria. However, the input to the method included possible motions for each part, and sets of other parts that interfere with each motion. No systematic way of generating the possible part motions was given, and the sequencer did no geometric computation.
A number of other approaches to automatic assembly sequencing have been proposed. One involved a number of heuristics to group parts of an assembly into subassemblies, but parts could only move along the major axes, and some operations may not be found. Another generated disassembly sequences involving complicated motions. However, some assembly sequences can be missed, and the directions of motion were required as input.
MOTION PLANNING
An assembly sequencing problem can be seen as a motion planning problem with multiple moving objects. Each part can be viewed as an independent robot, and a collision-free path must be found for the individual parts to move from an unassembled state to the assembled state. However, the general motion planning problem is known to take time exponential in the number of degrees of freedom; for an assembly of n rigid parts this formulation yields 6n degrees of freedom, so using a general path planning system in this naive way is impractical.
Motion planning plays a more limited role in determining feasible insertion trajectories for single assembly operations. Many general methods make assumptions that are not compatible with assembly planning, while answering more complex questions than are needed. For instance, some motion planning systems approximate the shapes of objects or assume the objects do not come in contact, both drawbacks for assembly planning.
Some motion planning methods have been developed specifically to suit the requirements of assembly planning. Valade found disassembly trajectories by calculating the interactions between concavities and objects and trying to reduce those interactions, until the parts were separated. Valade, "Geometric reasoning and automatic synthesis of assembly trajectory," Proc. Intl. Conf. On Advanced Robotics, pp. 43-50, 1985. In the preimage backchaining approach to fine-motion planning, the uncertainty of both sensing and control are modeled explicitly to find guaranteed plans to achieve a goal despite the high relative uncertainties present in assembly operations. Another method for analyzing insertion of flexible parts modeled them as compliant connections between rigid bodies.
The above methods are useful to verify the feasibility of individual assembly operations. Unfortunately, they all require that a large number of assembly operations be generated and then tested; none supply a way to generate only those operations that satisfy the constraints.
COMPUTATIONAL GEOMETRY
Research in computational geometry addresses limited cases of geometric assembly sequencing. Arkin et al. used the concept of a monotone path between obstacles to deduce a removable subassembly and a single extended translation to remove it. Arkin et al., "On monotone paths among obstacles, with applications to planning assemblies," Proc. 5th ACM Symp. on Computational Geometry, pp. 334-343, 1989. However, the parts were limited to polygons in the plane, and the extension to three dimensions is not obvious. Pollack et al. considered sequences of translations to separate polygons. Pollack et al., "Separating two simple polygons by a sequence of translations," Discrete and Computational Geometry, 3:123-136, 1988. The algorithm is limited to planar assemblies of two parts, but is able to find separating motions consisting of several distinct translations. Most of these methods are limited to two dimensions or allow only polyhedral parts; in addition, it is unclear how additional constraints, for instance arising from clamping forces or stability, can be included.
SUMMARY
Current methods for evaluating the manufacturing aspects of a product design can require extensive human judgment, and designers complain that they are tedious to use. One current planning system requires computationally expensive determinations of mating paths for each trial assembly. Lee, U.S. Pat. No. 5,442,563. Another uses an AND/OR graph to unfold all the assembly/disassembly steps that might be followed. Jeong, U.S. Pat. No. 5,523,960. The AND/OR graphs of realistic assemblies are generally far too complicated for timely planning. A fast, automatic assembly planning system would allow a designer to ask "what if" questions, quickly find the consequences of design decisions, and more easily evaluate the manufacturing impact of alternative designs.
Small batch manufacturing requires that assembly machines, people, and processes switch from one product to another quickly and often. An automated assembly planning system can help to merge the assembly schemes for several products and allow faster changeover. In addition, small batch size only amplifies the importance of low capital costs and fast creation of a manufacturing process.
A hybrid system, allowing a human to work in tandem with an automated assembly planner, could relieve the engineer from much of the repetitive and tedious work of devising an assembly plan. Meanwhile, the computer would check the human reasoning for consistency. A more competent, efficient, and accurate assembly planning system would result.
An automated assembly planning system can have great utility in both concurrent engineering and more mainstream manufacturing planning. There is a need for an automated assembly planning system that has the following characteristics:
Autonomy. Using the assembly planning system must require minimal effort from the designer. A human will quickly tire of doing detailed geometric reasoning, or even supplementing the assembly model to help the assembly planning system. As a result, the assembly planning system should build its model of the target assembly from readily available data, such as a CAD model of the product. Furthermore, the assembly planning system must include automated geometric and physical reasoning capabilities to allow it to generate assembly plans from just the assembly model given by a designer. Any required human input should be sparse, be useful to the designer, and lack tedium.
Accuracy. If an assembly planning system returns bad assembly plans or fails to find plans when they exist, it will quickly lose what little trust the human will place in the computer. Thus the employed geometric reasoning methods cannot ignore important details, the search algorithms must be correct and complete, and approximations must be relevant to the assembly planning domain.
Speed. If the engineer has to wait a long time to get assembly feedback from the system, it will be used infrequently, and the advantages of concurrent design will be lost.